Course Overview: This course is an introduction to the theory of computation, the branch of computer science that seeks to understand which problems can be solved by computational devices and how efficiently those problems can be solved. To make precise statements and rigorous arguments, we model computational devices using abstract mathematical models of computation.
Instructor: Alexander Poremba — poremba@bu.edu
Teaching Assistant: Rafay Cheema — cheema@bu.edu
Course links:
Piazza |
Gradescope
Assessment dates:
Time: Tuesday and Thursday, 12:30–1:45 p.m.
Location: CAS 216, 685–725 Commonwealth Avenue
Class dates: 09/03/2026–12/10/2026
First meeting: Thursday, 09/03/2026
Discussion/lab sections: See MyBU Student.
Regular deadlines: Unless stated otherwise, homework is due on Thursdays at 11:59 p.m. Every regularly scheduled Tuesday lecture ends with a quiz during the final ten minutes.
Prerequisites: CAS CS 131 (Combinatoric Structures) and CAS CS 330 (Introduction to Algorithms). If you have not completed the prerequisites, contact the instructor as soon as possible.
Below is the tentative course schedule. Topics may move as the semester develops, and any change will be announced in class and on Piazza. “Sipser” refers to the main textbook.
Calendar note: Tuesday, October 13 follows a Monday schedule of classes.
Thanksgiving: Recess runs Wednesday, November 25 through Sunday, November 29.
| Date | Topic | Reading / Reference |
|---|---|---|
| Thu 09/03 | Welcome and introduction | Sipser 0 |
| Tue 09/08 (Quiz) | Sets, strings, and languages | Sipser 0 |
| Thu 09/10 | Finite automata | Sipser 1.1–1.2 |
| Tue 09/15 (Quiz) | More on NFAs; DFA–NFA equivalence | Sipser 1.2 |
| Thu 09/17 | Closure properties and regular expressions | Sipser 1.2–1.3 |
| Tue 09/22 (Quiz) | Regular expressions versus finite automata | Sipser 1.3 |
| Thu 09/24 | Distinguishable sets and non-regular languages | Myhill–Nerode |
| Tue 09/29 (Quiz) | More non-regularity; Test 1 review | |
| Thu 10/01 | Test 1 | — |
| Tue 10/06 (Quiz) | Turing machines | Sipser 3.1, 3.3 |
| Thu 10/08 | Turing-machine variants, nondeterministic TMs, and closure properties | Sipser 3.2 |
| Tue 10/13 | No class — substitute Monday schedule | — |
| Thu 10/15 | Church–Turing thesis and decidability | Sipser 3.3, 4.1 |
| Tue 10/20 (Quiz) | More decidable languages, universal Turing machines, and countability | Sipser 4.1, 4.2 |
| Thu 10/22 | Uncountability, diagonalization, and undecidability | Sipser 4.2 |
| Tue 10/27 (Quiz) | More undecidability and unrecognizability; reductions | Sipser 4.2, 5.1 |
| Thu 10/29 | Examples of reductions and mapping reductions | Sipser 5.1, 5.3 |
| Tue 11/03 (Quiz) | More mapping reductions and asymptotic notation | Sipser 5.3, 7.1 |
| Thu 11/05 | Time and space complexity; hierarchy theorems | Sipser 7.1–7.2, 8.0, 9.1 |
| Tue 11/10 (Quiz) | Test 2 review | |
| Thu 11/12 | Test 2 | — |
| Tue 11/17 (Quiz) | Complexity class P | Sipser 7.2 |
| Thu 11/19 | Complexity class NP | Sipser 7.3 |
| Tue 11/24 (Quiz) | NP-completeness | Sipser 7.4–7.5 |
| Thu 11/26 | No class — Thanksgiving recess | — |
| Tue 12/01 (Quiz) | More NP-completeness | Sipser 7.4–7.5 |
| Thu 12/03 | Space complexity | Sipser 8.1–8.2 |
| Tue 12/08 (Quiz) | More on space complexity | Sipser 8.1–8.2 |
| Thu 12/10 | Course wrap-up and final review | |
| Thu 12/17 | Final examination, noon–2:00 p.m. (tentative) | — |
The learning objectives of the course are to:
The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church’s thesis, universal algorithms, undecidability and intractability, time and space complexity, nondeterminism, probabilistic computation, and reductions between computational problems.
Your final course grade is determined by tests, homework, quizzes, and participation.
| Component | Weight |
|---|---|
| Tests (total) | 60% |
| Test 1 | 17% |
| Test 2 | 17% |
| Comprehensive final exam | 26% |
| Homework | 15% |
| Quizzes | 15% |
| Participation | 10% |
The following letter grades are guaranteed for the corresponding final percentages. To account for the possibility that assignments or tests are more difficult than anticipated, final cutoffs may be lowered, but they will not be raised.
| Letter Grade | Guaranteed Minimum |
|---|---|
| A | ≥ 90% |
| A− | ≥ 85% |
| B+ | ≥ 80% |
| B | ≥ 75% |
| B− | ≥ 70% |
| C+ | ≥ 65% |
| C | ≥ 60% |
Test 1 is scheduled for Thursday, October 1, and Test 2 is scheduled for Thursday, November 12. Each test will take place during the normal class period and will cover roughly one-third of the course. The final examination is comprehensive. The current University matrix places the final on Thursday, December 17, from 12:00–2:00 p.m.; the official date, time, and room listed in MyBU Student are authoritative. Do not make end-of-semester travel plans until the University schedule is final.
You may bring one double-sided 8.5-by-11-inch sheet of notes to each in-class test and two such sheets to the final. Note sheets may be handwritten or typeset. No other aids are permitted, including books, lecture notes, calculators, phones, tablets, laptops, or other electronic devices.
There will be regular homework assignments. Unless an assignment states otherwise, homework is due on Thursdays at 11:59 p.m. on Gradescope. No late homework will be accepted without prior arrangement. To accommodate an occasional difficult week or extenuating circumstance, the lowest homework grade will be dropped.
You are allowed, and encouraged, to collaborate with other students while developing ideas for most homework problems. After discussing a problem, however, you must write the solution independently and in your own words. You may not copy, share, or consult another student’s written solution. Some assignments may contain clearly marked individual review problems; no collaboration is allowed on those problems.
Some assignments may include optional challenge problems. These problems do not directly change the homework average, but sustained, high-quality work on them may be considered when a final course percentage lies exactly on a letter-grade boundary.
An in-class quiz will take place during the final ten minutes of every Tuesday lecture. Quizzes are closed-book and closed-device. They will contain short questions about lecture material from the previous week as well as material from discussion/lab sections.
The questions are intended to be straightforward checks that you are following the course. If you actively follow lecture, attend discussion/lab, and complete the homework, you should not need to devote additional study time to prepare for the quizzes. Nevertheless, you are encouraged to refresh your memory before every Tuesday class.
If you miss a Tuesday lecture, you will receive a score of zero for that day’s quiz. At the end of the semester, the four lowest quiz grades will be dropped. University-required accommodations will be honored.
Active participation in lecture and discussion/lab is an essential part of learning the material. The participation grade includes constructive engagement during class and timely submission of discussion worksheets. You may increase your participation score by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.
Attendance is not a separate grading category, but absences can directly affect quizzes, discussion worksheets, and meaningful participation. Students are expected to attend every class session and are responsible for material and announcements missed during an absence.
Michael Sipser, Introduction to the Theory of Computation, 3rd edition, ISBN-13 978-1133187790.
A list of errata is available from the author’s errata page.
Reading the textbook before class and reviewing it after class are important for solidifying your understanding. An older edition is acceptable, although section numbering may differ. The price of the textbook should not be a barrier to your learning; contact the instructor if the cost presents a hardship.
You are encouraged to typeset homework solutions in LaTeX, the standard document-preparation system in the mathematical sciences. LaTeX makes it easier to revise your work and helps the course staff read and evaluate mathematical arguments. I recommend using Overleaf because it runs in a web browser and requires no local installation.
The course website contains the syllabus, schedule, assigned readings, homework assignments, and other course materials.
All class announcements will be made through Piazza, so set your notification preferences accordingly. Questions about course material should ordinarily be posted there rather than sent privately to course staff; other students are likely to have the same question and may be able to respond quickly.
Homework will be submitted in PDF format through Gradescope. Use your BU email address when creating or joining the course account. Grades and regrade requests will also be managed there.
Collaboration is intended to help you learn, not to divide the work. Permitted collaboration includes discussing definitions, examples, the meaning of a problem, and high-level approaches. Every submitted proof and solution must reflect your own understanding and must be written independently. When in doubt about whether a form of collaboration is allowed, ask the instructor before submitting the work.
No AI may be used to solve graded homework problems.
The process of struggling with a problem, testing ideas, finding a useful representation, and turning an argument into a clear proof is a central part of this course. That process is also the practice that prepares you for closed-book quizzes and exams. Using an AI system to skip ahead to an approach or solution creates the appearance of progress while removing the very practice the assignment is designed to provide.
For graded homework, do not paste or paraphrase a problem into an AI system, and do not use AI output to interpret, plan, solve, verify, rewrite, or polish any part of your solution. Generic questions about LaTeX syntax are permitted only when they do not reveal the homework problem or your solution.
AI tools may be used privately for learning that is not tied to a specific graded problem—for example, to request another explanation of a general concept, to see an unrelated example, or to generate additional practice questions. AI output can be inaccurate; you remain responsible for checking anything you use for personal study.
All Boston University students are expected to maintain high standards of academic honesty and integrity. It is your responsibility to know and follow the Boston University Academic Conduct Code, which describes the University’s ethical expectations and students’ rights and responsibilities. Cheating, plagiarism, unauthorized collaboration, misrepresentation of work, and other forms of academic misconduct will be addressed under that policy.
Gradescope provides a mechanism for requesting regrades. Regrade requests will be accepted for one week after a homework assignment or test is returned. Before submitting a request, read the posted solution and grading rubric carefully. A request must identify a specific factual error in how the grader interpreted your work; requests based only on disagreement about the number of points associated with a mistake cannot be accommodated. The entire submission may be reviewed when a regrade is requested.
Boston University expects students to attend every class session. If illness or another serious circumstance requires you to miss class, notify the instructor as soon as possible, ideally before the absence, and make a plan to keep up with the course. The University’s attendance policy is available online.
Students who must miss class or an assessment because of religious observance will not be penalized and will be given a reasonable opportunity to make up affected work, consistent with the University’s Absence for Religious Reasons policy. Notify the instructor as early as possible.
In the event of the death of a close family member, contact your academic advisor and the instructor. The University’s Student Bereavement policy provides up to five weekdays of bereavement leave; requests for additional time are handled through the student’s school or college.
Students with disabilities who need academic accommodations should contact Disability & Access Services (DAS), 25 Buick Street, Suite 300, at 617-353-3658 or access@bu.edu. If you receive an accommodation letter, share it with the instructor promptly and sufficiently in advance of the relevant assessment so that arrangements can be made.
Questions about a grade should first be discussed with the grader or instructor. A formal appeal of an allegedly arbitrary final course grade is governed by the University’s undergraduate grade-grievance policy.
An Incomplete is appropriate only in limited circumstances when a student has completed a substantial majority of the course but cannot finish the remaining work for an acceptable reason. The student must confer with the instructor before final grades are submitted, and both parties must complete the required report specifying the remaining work and deadline. See the University’s Incomplete Coursework policy.
Student Health Services provides medical care, mental-health services, wellness education, and other support. Students considering a medical leave should consult Student Health Services, their advisor, and the University’s leave-of-absence policy.
The International Students & Scholars Office supports international students with immigration documentation, visas, and adjustment to the Boston University community.
Syllabus changes. This syllabus is subject to change when doing so will better serve the needs of the class. Any substantive change will be announced in class and posted on Piazza and the course website.